using System;

namespace LeetCode {
    public class BST {
        public int NumTrees (int n) {
            int[] v = new int[n + 1];
            v[0] = 1;
            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= i - 1; j++)
                    v[i] += v[j] * v[i - (j + 1)];
            }
            return v[n];
        }
        public int numTrees1 (int n) {
            int[] G = new int[n + 1];
            G[0] = 1;
            G[1] = 1;

            for (int i = 2; i <= n; ++i) {
                for (int j = 1; j <= i; ++j) {
                    G[i] += G[j - 1] * G[i - j];
                }
            }
            return G[n];
        }
        public int numTrees2 (int n) {
            int res = 0;
            if (n == 0 || n == 1) {
                return 1;
            }
            for (int i = 1; i < n + 1; i++) {
                res += numTrees2 (i - 1) * numTrees2 (n - i);
            }
            return res;
        }
    }
}